This invention relates to global positioning, and more particularly to the issue of confidence that a user has in global positioning information that equipment may provide. In the context of this disclosure, global positioning encompasses the absolute geo-location as well are the relative location of one object relative to another object.
There are numerous electronic ways by which global positioning may be provided. Some are terrestrial, and some are based on satellites. A satellite system that currently is most commonly used is the Global Positioning System (GPS), and it is quite well known in the sense that many people have GPS receivers that assist them in determining their physical location. GPS uses a collection of satellites that are arranged to orbit the Earth so that at least four satellites are always within the reception range of a receiver, at any point on the globe. One of the signals that the satellites transmit is a signal at frequency L1, which is used as a carrier to modulate a data signal that is itself modulated with a Code Division Multiple Access (CDMA) code, commonly referred to as the C/A code. The CDMA code that is used by each satellite is unique to the satellite, but it is publicly known, which allows the receiver to discriminate, or detect, the individual signal of each of the satellites in the presence of signals from the other satellites and in the presence of noise. Actually, each satellite transmits at least one other signal, employing the same carrier frequency that is shifted 90 degrees. This second signal is modulated by another code, known as the P(Y) code. The P(Y) code is either the P, which is publicly known, or the encrypted Y code. Today, all satellites use the Y code and, consequently, the resulting transmitted signal that is encoded with the Y code cannot be used by anyone other than those who have the decryption algorithm and the key. Each satellite transmits yet another signal, on frequency L2, but the disclosure herein focuses on frequency L1 only. It should be understood that the principles disclosed herein apply to L1, L2, or any of the new frequencies that are planned for satellite navigation.
Because the invention that is disclosed herein is illustrated by way of an example that is based on the pervasive GPS system, the following gives an abbreviated review of the GPS signals and the processing that takes place in a conventional GPS receiver. It should be kept in mind that the deficiency in the GPS system that is mentioned later is found in all other non-encrypted systems, and that the applicability of the invention disclosed herein extends beyond the GPS system. It should be kept in mind, therefore, that terms referring to global positioning (without initial letters being capitalized) refers to the terms generically, and not necessarily solely to GPS.
A conventional GPS receiver, shown in FIG. 1, simultaneously receives a number of satellite signals on frequency L1, where the signal transmitted by satellite n can be expressed asStransmitted=AnDn(t)xC/An(t)cos(2π(fL1)t+φ1)+BnDn(t)xYn(t)sin(2π(fL1)t+φ1)  (1)where Dn(t) is the data signal, xC/An (t) is the C/A code signal assigned to satellite n, fL1 is the frequency of the carrier, and φ1 is the phase of the carrier relative to the beginning of the data and code signals.
A GPS receiver can engage in the processing of signals as if all of the possible satellites are present but, of course, some of the satellites are not within range of the GPS receiver's antenna so the processing results for those satellites are not viable. The following analysis follows the signal of only one satellite and, for sake of simplicity, superscript n is omitted from the equations, and the C/A subscript is shortened to C.
The transmitted signal is subjected to transit time delay to the receiver, τ, and the signal that is received by a receiver's antenna experiences a Doppler frequency shift, fD, due to the satellite's movement in its orbit and possible receiver motion. Also, the transmitter and the receiver do not have a common clock, which means that even when the transmitter and the receiver clocks are at identical frequency, there is, nevertheless, a phase difference between them. Thus, the received signal thus can be expressed asSreceived=AD(t−τ)xC(t−τ)cos(2π(fL1+fD)(t−τ)+φ1)+BD(t−τ)xY(t−τ)sin(2π(fL1+fD)(t−τ)+φ1)  (2)or simplified toSreceived=AD(t−τ)xC(t−τ)cos(2π(fL1+fD)t+φ1−φ2)+BD(t−τ)xY(t−τ)sin(2π(fL1+fD)t)+φ1−φ2)  (3)
As shown in FIG. 1, the received signal is amplified in element 10, conventionally downshifted to a preselected intermediate frequency (IF) by multiplying the received signal in element 12 by signalsin(2π(fL1+fIF)t+φ3)  (4)and passing the resulting signal through low pass filter 15. The signal of equation (4) is generated from reference oscillator 20 by frequency synthesizer 22, where φ3 is the phase of the locally generated signal (relative to the beginning of the data and code signals at the transmitting satellite which, of course, is unknown). The result at the output of the low pass filter isSdownshifted=AD(t−τ)xC(t−τ)cos(2π(fIF+fD)t+φ1−φ2−φ3)+BD(t−τ)xY(tτ)sin(2π(fIF+fD)t+φ1−φ2−φ3)  (5)or simplified toSdownshifted=AD(t−τ)xC(t−τ)cos(2π(fIF+fD)t+θ1)+BD(t−τ)xY(t−τ)sin(2π(fIF+fD)t+θ1).  (6)
It may be noted that the above-described use of downshifting by use of an IF modulator 12 and low pass filter 15 is illustrative, and that the A/D can be connected directly to amplifier 10 and controlled to generate a digital signal as if it were downshifted as shown in FIG. 1.
The output signal of low pass filter 15 is digitized in A/D converter 18 and applied to a combination of processor 100 and associated memory 110 where the remainder of the processing takes place.
The processing begins with a signal acquisition (software) module that includes a code generator element and a carrier generation module. The code generation module develops signalxC(t−{circumflex over (τ)}),  (7)where {circumflex over (τ)} is an estimate of τ, and the carrier generator module creates two signals that may be viewed as the phasorΨ=cos(2π(fIF+{circumflex over (f)}D)t+θ1)−i sin(2π(fIF+{circumflex over (f)}D)t+θ1),  (8)where {circumflex over (f)}D is an estimate of the Doppler frequency shift fD, and {circumflex over (θ)}1 is an estimate of the phase θ1. Multiplying the received (and downshifted) signal of equation (6) by the code signal of equation (7) and the phasor of equation (8) and then integrating the product over a preselected interval that is long enough to reliably detect a correlation peak (for example, more than one period of the C/A code) yields:∫FCΨ cos(2π(fIF+fD)t+θ1)]+∫FYΨ sin(2π(fIF+fD)t+θ1)]  (9)whereFC=AD(t−τ)xC(t−τ)xC(t−{circumflex over (τ)}) and FY=BD(t−τ)xY(t−τ)xC(t−{circumflex over (τ)})  (10)Equation (9) expands to
                                          S            I                    +                      S            Q                          =                              ∫                                          F                C                            ⁢                              {                                                                                                                                                          cos                            ⁡                                                          (                                                                                                2                                  ⁢                                                                      π                                    ⁡                                                                          (                                                                                                                        f                                          IF                                                                                +                                                                                                                              f                                            ^                                                                                    D                                                                                                                    )                                                                                                        ⁢                                  t                                                                +                                                                                                      θ                                    ^                                                                    1                                                                                            )                                                                                ⁢                                                      cos                            ⁡                                                          (                                                                                                2                                  ⁢                                                                      π                                    ⁡                                                                          (                                                                                                                        f                                          IF                                                                                +                                                                                  f                                          D                                                                                                                    )                                                                                                        ⁢                                  t                                                                +                                                                  θ                                  1                                                                                            )                                                                                                      -                                                                                                                                                i                        ⁢                                                                                                  ⁢                                                  sin                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        IF                                                                            +                                                                                                                        f                                          ^                                                                                D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                                                                θ                                  ^                                                                1                                                                                      )                                                                          ⁢                                                  cos                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        IF                                                                            +                                                                              f                                        D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                              θ                                1                                                                                      )                                                                                                                                              }                                              +                      ∫                                          F                Y                            ⁢                              {                                                                                                                                                          cos                            ⁡                                                          (                                                                                                2                                  ⁢                                                                      π                                    ⁡                                                                          (                                                                                                                        f                                          IF                                                                                +                                                                                                                              f                                            ^                                                                                    D                                                                                                                    )                                                                                                        ⁢                                  t                                                                +                                                                                                      θ                                    ^                                                                    1                                                                                            )                                                                                ⁢                                                      sin                            ⁡                                                          (                                                                                                2                                  ⁢                                                                      π                                    ⁡                                                                          (                                                                                                                        f                                          IF                                                                                +                                                                                  f                                          D                                                                                                                    )                                                                                                        ⁢                                  t                                                                +                                                                  θ                                  1                                                                                            )                                                                                                      -                                                                                                                                                i                        ⁢                                                                                                  ⁢                                                  sin                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        IF                                                                            +                                                                                                                        f                                          ^                                                                                D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                                                                θ                                  ^                                                                1                                                                                      )                                                                          ⁢                                                  sin                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        IF                                                                            +                                                                              f                                        D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                              θ                                1                                                                                      )                                                                                                                                              }                                                                        (        11        )            or to
                                          S            I                    +                      S            Q                          =                              ∫                                          F                C                            ⁢                              {                                                                                                                              cos                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  2                                        ⁢                                                                                  f                                          IF                                                                                                                    +                                                                              f                                        D                                                                            +                                                                                                                        f                                          ^                                                                                D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                              θ                                1                                                            +                                                                                                θ                                  ^                                                                1                                                                                      )                                                                          +                                                                                                                                                                          cos                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        D                                                                            -                                                                                                                        f                                          ^                                                                                D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                              θ                                1                                                            -                                                                                                θ                                  ^                                                                1                                                                                      )                                                                          -                                                                                                                                                                          i                          ⁢                                                                                                          ⁢                                                      sin                            ⁡                                                          (                                                                                                2                                  ⁢                                                                      π                                    ⁡                                                                          (                                                                                                                        2                                          ⁢                                                                                      f                                            IF                                                                                                                          +                                                                                  f                                          D                                                                                +                                                                                                                              f                                            ^                                                                                    D                                                                                                                    )                                                                                                        ⁢                                  t                                                                +                                                                  θ                                  1                                                                +                                                                                                      θ                                    ^                                                                    1                                                                                            )                                                                                                      +                                                                                                                                                i                        ⁢                                                                                                  ⁢                                                  sin                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        D                                                                            -                                                                                                                        f                                          ^                                                                                D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                              θ                                1                                                            -                                                                                                θ                                  ^                                                                1                                                                                      )                                                                                                                                              }                                              +                      ∫                                          F                y                            ⁢                                                {                                                                                                                                          sin                            ⁡                                                          (                                                                                                2                                  ⁢                                                                      π                                    ⁡                                                                          (                                                                                                                        2                                          ⁢                                                                                      f                                            IF                                                                                                                          +                                                                                  f                                          D                                                                                +                                                                                                                              f                                            ^                                                                                    D                                                                                                                    )                                                                                                        ⁢                                  t                                                                +                                                                  θ                                  1                                                                +                                                                                                      θ                                    ^                                                                    1                                                                                            )                                                                                +                                                                                                                                                                                          sin                            ⁡                                                          (                                                                                                2                                  ⁢                                                                      π                                    ⁡                                                                          (                                                                                                                        f                                          D                                                                                -                                                                                                                              f                                            ^                                                                                    D                                                                                                                    )                                                                                                        ⁢                                  t                                                                +                                                                  θ                                  1                                                                -                                                                                                      θ                                    ^                                                                    1                                                                                            )                                                                                +                                                                                                                                                                                          i                            ⁢                                                                                                                  ⁢                                                          cos                              ⁡                                                              (                                                                                                      2                                    ⁢                                                                          π                                      ⁡                                                                              (                                                                                                                              2                                            ⁢                                                                                          f                                              IF                                                                                                                                +                                                                                      f                                            D                                                                                    +                                                                                                                                    f                                              ^                                                                                        D                                                                                                                          )                                                                                                              ⁢                                    t                                                                    +                                                                      θ                                    1                                                                    +                                                                                                            θ                                      ^                                                                        1                                                                                                  )                                                                                                              -                                                                                                                                                              i                          ⁢                                                                                                          ⁢                                                      cos                            ⁡                                                          (                                                                                                2                                  ⁢                                                                      π                                    ⁡                                                                          (                                                                                                                        f                                          D                                                                                -                                                                                                                              f                                            ^                                                                                    D                                                                                                                    )                                                                                                        ⁢                                  t                                                                +                                                                  θ                                  1                                                                -                                                                                                      θ                                    ^                                                                    1                                                                                            )                                                                                                                                                            }                                .                                                                        (        12        )            Since, as indicated above,FY=BD(t−τ)xY(t−τ)xC(t−{circumflex over (τ)}),  (13)and the C/A code is orthogonal to the Y code, the second integral of equation (12) yields zero. Also, the integration acts like a low pass filter that discards the high frequency signals of cos2π(2fIF+fD+{circumflex over (f)}D)t and sin2π(2fIF+fD+{circumflex over (f)}D)t, leaving
                                          S            I                    +                      iS            Q                          =                  ∫                                    F              C                        ⁢                                          {                                                                                                    +                                                  cos                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        D                                                                            -                                                                                                                        f                                          ^                                                                                D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                              θ                                1                                                            -                                                                                                θ                                  ^                                                                1                                                                                      )                                                                                                                                                                                                                            +                          i                                                ⁢                                                                                                  ⁢                                                  sin                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        D                                                                            -                                                                                                                        f                                          ^                                                                                D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                              θ                                1                                                            -                                                                                                θ                                  ^                                                                1                                                                                      )                                                                                                                                              }                            .                                                          (        14        )            It can be demonstrated that S12+SQ2 equals
                                                                                          S                  I                  2                                +                                  S                  Q                  2                                            =                            ⁢                                                                    (                                          ∫                                                                        F                          C                                                ⁢                                                  cos                          ⁡                                                      (                                                                                          2                                ⁢                                                                  π                                  ⁡                                                                      (                                                                                                                  f                                        D                                                                            -                                                                                                                        f                                          ^                                                                                D                                                                                                              )                                                                                                  ⁢                                t                                                            +                                                              θ                                1                                                            -                                                                                                θ                                  ^                                                                1                                                                                      )                                                                                                                )                                    2                                +                                                                                                      ⁢                                                (                                      ∫                                                                  F                        C                                            ⁢                                              sin                        ⁡                                                  (                                                                                    2                              ⁢                                                              π                                ⁡                                                                  (                                                                                                            f                                      D                                                                        -                                                                                                                  f                                        ^                                                                            D                                                                                                        )                                                                                            ⁢                              t                                                        +                                                          θ                              1                                                        -                                                                                          θ                                ^                                                            1                                                                                )                                                                                                      )                                2                                                                                        =                            ⁢                                                                    (                                          ∫                                                                        F                          C                                                ⁢                        cos                        ⁢                                                                                                  ⁢                        2                        ⁢                                                  π                          ⁡                                                      (                                                                                          f                                D                                                            -                                                                                                f                                  ^                                                                D                                                                                      )                                                                          ⁢                        t                                                              )                                    2                                +                                                                                                      ⁢                                                (                                      ∫                                                                  F                        C                                            ⁢                      sin                      ⁢                                                                                          ⁢                      2                      ⁢                                              π                        ⁡                                                  (                                                                                    f                              D                                                        -                                                                                          f                                ^                                                            D                                                                                )                                                                    ⁢                      t                                                        )                                2                                                                        (        15        )            which is independent of (θ1−{circumflex over (θ)}1). It can be also demonstrated that good estimates for τ, and fD are attained when code generation module is adjusted as to introduce a delay, {circumflex over (τ)}, and the carrier generator module is adjusted as to the introduced {circumflex over (f)}D so as to maximize S12+SQ2.
For the more visually inclined reader, FIG. 2 shows a diagrammatic representation of the processing that takes place in the acquisition module.
The task of the acquisition module is to come up with a first-cut approximation of the delay and the Doppler frequency shift. A refinement of the approximations takes place in a tracking module, whose function is to both refine the estimates and track the changes in τ, fD and θ1 as conditions change, and whose diagrammatic representation is shown in FIG. 3.
The tracking module contains a phase lock loop comprising multiplier 31 that multiplies the Sdownshifted signal of equation (6) by the phasor of equation (8) provided by numerically controlled oscillator (carrier NCO) 32. The output of multiplier 31 is multiplied in multiplier 33 by the code signal obtained from code generator 38. The output of multiplier 33 is integrated in module 34 and applied to discriminator 35, which develops a carrier error signal (θ1−{circumflex over (θ)}1) that controls the frequency of the carrier NCO.
The output of multiplier 31 is also applied to multiplier 36, where it is multiplied by the code signal that is generated by element 38, but delayed by half of the duration of code C/A chip; i.e.,xC(t−{circumflex over (τ)}−TC/2)  (16)and to multiplier 37, where it is multiplied by the code signal that is generated by element 38, but advanced by half of the duration of code C/A chip; i.e.,xC(t−{circumflex over (τ)}+TC/2)  (17)The outputs of multipliers 36 and 37 are integrated in elements 41 and 42, respectively, and applied to discriminator 39 which develops a delay error signal (t−{circumflex over (τ)}) that is applied to code generator 38, controlling the frequency of the clock that generates the code.
While in both elements 32 and 38 the frequency of a clock is controlled by the respective discriminators, the result is that the generated carrier frequency phasor that is applied to multiplier 31 is in the formcos(2π(fIF+{circumflex over (f)}D)t+{circumflex over (θ)}1)−i sin(2π(fIF+{circumflex over (f)}D)t+{circumflex over (θ)}1  (18)with the approximations {circumflex over (f)}D and {circumflex over (θ)}1 tracking closely the fD and θ1 of equation (6), and the generated codexC(t−{circumflex over (τ)})  (19)has a {circumflex over (τ)} that is a close estimate of τ.
The code and the carrier measurement are applied to subsequent modules (not shown) that decode the navigation message, determine satellite ephemeris, and compute the pseudo-range, and with corresponding pseudo-ranges obtained by processing other satellites, the physical location of the receiver is computed (through quadralateration) and displayed.
All of the above is conventional, and the reader is invited to peruse the book “Global Positioning System” by Misra and Enge, Ganga-Jamuna Press, 2006 for further details. In general, the GPS literature is enormous. It describes alternate implementation to the above, where, for example, the code and carrier removal processes described by equations (7), (8) and (9) are done in different order. It also describes implementations that use correlator spacings other than those chosen in equations (16) and (17). The literature is also replete with discriminator strategies that differ from the simple “early minus late” strategy described here.
In commercial applications the C/A code is publicly known and, consequently, GPS receivers are vulnerable to spoofing. A hostile party can generate a facsimile of one or more satellite signals that carry incorrect information, and a GPS receiver that accepts the bogus signals will compute an incorrect position and, in fact, may be caused to compute a position that the hostile party wishes to have the receiver compute. However, spoofing is not a problem for those who are able to use the Y code because this code is not publicly known, so a hostile party cannot create a signal that appears bona fide. This problem is not unique to GPS receivers, of course. It is endemic to all global positioning systems that rely on insecure signals.
The primary object of this disclosure is to create a method and a means for having confidence that a global position computation, or an assertion based on a global position, is bona fide.
Another object of this disclosure is to have global positioning computation devices, such as GPS receivers that, without having access to the information contained in a secure signal, or access to the code that makes the information secure (henceforth, the unknown signal), such as the Y code in the GPS signal, are nevertheless able to withstand spoofing attempts, for example an attack by a rogue user with access to an authorized receiver or an attack by a malicious agent attempting to dupe legitimate users.
Yet another object of this invention is to determine the location of a device by processing the unknown signal jointly at the two stations (or locations).
Still another object of this invention is to authenticate a claim regarding a location that such a computing device asserts in connection with information services, such as financial services.